package kaiao.dynamic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class 杨辉三角 {

	public static void main(String[] args) {

	}


	// 先找到杨慧三角规律，再根据规律动态计算，因为是输出数组，可将数组先写出然后再比较规律
	public List<List<Integer>> generate(int numRows) {

		// 先预定行数
		List<List<Integer>> result = new ArrayList<>(numRows);

		// 添加第一行基础参数
		result.add(Arrays.asList(1));

		// 循环分配空间 i为行指针 j为列指针
		for (int i = 1; i < numRows; i++) {
			List<Integer> row = new ArrayList<>(i + 1);
			List<Integer> lastRow = result.get(i - 1);

			row.add(1);
			// 添加行中数据
			for (int j = 1; j < i; j++) {
				row.add(lastRow.get(j) + lastRow.get(j-1));
			}

			row.add(1);

			result.add(row);
		}

		return result;
	}
}
